package linkedlist;

/**
 * @author tongchen
 * @create 2022-09-28 12:50
 */
public class LinkedListTest {
    public static void main(String[] args) {
        Node node = new Node(2);
        LinkedList linkedList = new LinkedList(node);
      //  LinkedList linkedList1 = new LinkedList();
        //System.out.println(linkedList1.size());
        linkedList.addFirst(3);
        linkedList.addFirst(3);
        linkedList.addLast(8);
        linkedList.addLast(4);
        linkedList.addLast(5);
    linkedList.display();
        System.out.println(linkedList.size());
        linkedList.removeAllKey(8);
        linkedList.remove(3);
        linkedList.display();
        System.out.println(linkedList.contains(5));
        System.out.println(linkedList.contains(3));
        System.out.println(linkedList.contains(1));
        System.out.println(linkedList.find(3));
        System.out.println(linkedList.find(2));
        System.out.println(linkedList.find(9));
        System.out.println(linkedList.find(5));

    }

}
class LinkedList{
    public LinkedList() {
    }

    private static int counts;
    //设置根结点，往后的任何对链表操作的方法都是利用根结点进行操作的
    Node root;

    public LinkedList(Node root) {
        this.root = root;
    }

    // 1、无头单向非循环链表实现
 //头插法
        public void addFirst(int data){
            Node node = new Node(data);
            node.next=root;
            root=node;
        }
        //尾插法
        public void addLast(int data){
        //如果是第一个结点，先将头结点引用
            Node node = new Node(data);
            if (root==null){
                root=node;
                return;
            }
//第二个结点开始是完全意义上的尾插法
            Node cur=root;
            while (cur.next!=null){
                cur=cur.next;
            }
            //将最后一个结点插入
            cur.next=node;
        }

        //根据下标数据进行插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
        //设置中间结点进行循环
        Node temp=root;
        if (index<0||index>=size()){
            throw new IndexOutOfBoundsException("输入的下标不合法");
        }
        //第一个位置进行头插
        if (index==0){
            addFirst(data);
        }
        //在最后一个位置进行尾插
            if (index==size()-1){
                addLast(data);
            }
            //在中间位置进行插入
            for (int i=0;i<index-1;++i){

            }
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
        Node temp=root;
        while(temp!=null){
            if (temp.value==key){
                return true;
            }
            temp=temp.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
        public void remove(int key){
        Node temp=root;
        //如果要删除头结点，那么将头结点往后移动一位即可
        if (temp.value==key){
            root=root.next;
            return;
        }
        while(temp.next!=null){
            if (temp.next.value==key){
                temp.next=temp.next.next;
                break;
            }
            temp=temp.next;
        }
        }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        //优先处理头结点

        while (root!=null&&root.value==key){
            root=root.next;
        }
        if (root==null){
            return;
        }
        //处理中间结点
        Node pre=root;
        Node cur=pre.next;
        while (cur!=null){
            if (cur.value==key){
                pre.next=cur.next;
            }
            else {
                pre=cur;
            }
            cur=cur.next;
        }



    }
    //得到单链表的长度
    public int size(){

        int count=0;
        Node temp=root;
        if (root==null){
            System.out.println("链表为空，无法遍历");
            return -1;
        }
        while (temp!=null){
            count++;
            temp=temp.next;
        }
        return count;
    }
    public void clear() {
        if (root==null){
            return;
        }
       Node cur=root;
        while (cur!=null){
            Node next=cur.next;
            cur.next=null;
            cur=next;
        }
        root=null;
    }
    public void display() {


        Node temp=root;
        if (root==null){
            System.out.println("链表为空，无法遍历");
            return;
        }
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (temp!=null){

       sb.append(temp);
       if (temp.next!=null){
           sb.append(",");
       }
            temp=temp.next;
        }
        sb.append("]");
        System.out.println(sb);
    }
    //设置查找方法
    //需要注意的是：在查找完成之后，后面进行在特定位置添加操作时，需要分三种情况进行讨论（1.在最后一个位置2.在中间位置3.链表还没有达到该位置 ）
    public int find(int value){
        if (root==null){
            throw new RuntimeException("链表为空，不能在其中查找元素");
        }
       //设置计数器用于返回其下标
        int count=0;
        Node temp=root;
        while(temp!=null){
            if (temp.value==value){
                return count;
            }
            temp=temp.next;
            count++;
        }
        return -1;

    }


}
class Node{
    int value;
    //用来定义序号
    int num;
    Node next;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +'}';
    }
}
